\chapter{Parametric Yield Driven Resource Binding in Behavioral\\ Synthesis with Multi-$V_{th}/V_{dd}$
Library}\label{chapter:multiv}

The ever-increasing chip power dissipation in SoCs has imposed great challenges
on today's circuit design. It has been shown that multiple threshold and supply
voltages assignment (multi-$V_{th}/V_{dd}$)  is an effective way to reduce
power dissipation. However, most of the prior multi-$V_{th}/V_{dd}$
optimizations are performed under deterministic conditions. With the increasing
process variability that has significant impact on both the power dissipation
and performance of circuit designs, it is necessary to employ statistical
approaches in analysis and optimizations for low power. This chapter studies
the impact of process variations on the multi-$V_{th}/V_{dd}$ technique at the
behavioral synthesis level. A multi-$V_{th}/V_{dd}$ resource library is
characterized for delay and power variations at different voltage combinations.
A parametric yield-driven resource binding algorithm is then proposed, which
uses the characterized power and delay distributions and efficiently maximizes
power yield under a timing yield constraint. During the resource binding
process, voltage level converters are inserted between resources when required.
Experimental results show that significant power reduction can be achieved with
the proposed variation-aware framework, compared with traditional worst-case
based deterministic approaches.

\section{Introduction}\label{sec:C4-intro}

%Integrating billions of transistors on a single chip with nano-scale
%transistors has resulted in great challenges for chip designers. One of these
%challenges is that the pace of productivity gains has not kept up to address
%the increases in design complexity. Consequently, we have seen a recent trend
%of moving design abstraction to a higher level, with an emphasis on
%\textbf{Electronic System Level (ESL)} design methodologies. A very important
%component of ESL is raising the level of abstraction of hardware design.
%High-level synthesis (HLS) provides this component by providing automation to
%generate optimized hardware from a high-level description of the function or
%algorithm to be implemented in hardware. HLS generates a cycle-accurate
%specification at the register-transfer level (RTL) that is then used in
%existing ASIC or FPGA design methodologies. Commercial high-level synthesis
%tools~\cite{HLS:newbook} have recently gained a lot of attention as evidenced
%in recent conference HLS workshops (DATE2008, DAC2008, ASPDAC2009), conference
%panels and publications that track the industry.


Power consumption and process variability are among the critical design
challenges as technology scales. While it is believed that tackling these
issues at a higher level of the design hierarchy can lead to better design
decisions, a lot of work has been done on low-power high-level
synthesis~\cite{hls:shiue00, HLS:Khouri02, HLS:Tang05} as well as
process-variation aware high-level synthesis\cite{hls:weilun05, HLS:Jung07,
HLS:Wang08, HLS:Greg09}. These techniques have been successfully implemented
but most of the existing work focuses on one side of the issues in isolation.
Recently, Srivastava et al.\cite{HLS:Srivastava07} explore the
multi-$V_{th}/V_{dd}/T_{ox}$ design space with the consideration of process
variations at the gate level. Nevertheless, variation-aware low power
exploration for behavioral synthesis is still in its infancy.

Multiple threshold and supply voltages assignment (multi-$V_{th}/V_{dd}$) has
been shown as an effective way to reduce circuit power
dissipation~\cite{UsamiI00, hls:shiue00, HLS:Khouri02, HLS:Srivastava04}.
Existing approaches assign circuit components on critical paths to operate at a
higher $V_{dd}$ or lower $V_{th}$, and non-critical portions of the circuit are
made to operate at lower $V_{dd}$ or higher $V_{th}$, respectively. The total
power consumption is thus reduced without degrading circuit performance.
However, nowadays circuit performance is affected by process variations. If the
variations are under-estimated, for example, using nominal delays of circuit
components to guide the design, non-critical components may turn to critical
ones due to the variations, and circuit timing constraints may be violated. On
the other hand, in existing corner-based worst-case analysis, variations are
over-estimated resulting in design specs that are hard to meet, and this
consequently increases design effort and degrades circuit performance.

This chapter presents a variation-aware power optimization framework in
high-level synthesis using simultaneous multi-$V_{th}/V_{dd}$ assignments.
Firstly, the impact of parameter variations on the delay and power of circuit
components, is explored at different operating points of threshold and supply
voltages. A variation-characterized resource library containing the parameters
of delay and power distributions at different voltage ``corners'', is built
once for the given technology, so that is available for high-level synthesis to
query the delay/power characteristics of resources. The concept of
\emph{Parametric Yield}, which is defined as the probability that the design
meets specified constraints such as delay or power constraints, is then
introduced to guide design space exploration. Statistical timing and power
analysis on the data flow graph (DFG) is used to populate the delay and power
distributions through the DFG, and to estimate the overall performance and
power yield of the entire design. A variation-aware resource binding algorithm
is then proposed to maximize power yield under a timing yield constraint, by
iteratively searching for the operations that have the maximum potential of
performance/power yield improvement, and replacing them with better candidates
in the multi-$V_{th}/V_{dd}$ resource library. During the resource binding
process, voltage level converters are inserted for chaining of resource units
having different $V_{dd}$ supplies.

The contribution of this chapter can be summarized as:
\begin{itemize}
  \item First, this is the first work to apply multi-$V_{th}/V_{dd}$
      techniques during high-level synthesis under the context of both
      delay and power variations. A flow for variation-aware power
      optimization in multi-$V_{th}/V_{dd}$ HLS is proposed. This flow
      includes library characterization, statistical timing and power
      analysis methodologies for HLS, and resource binding optimization
      with variation-characterized multi-$V_{th}/V_{dd}$ library.
  \item Voltage level conversion is explored during the resource binding in
      high-level synthesis, enabling the full utilization of multi-$V_{dd}$
      components.
\end{itemize}

%\vspace{5pt}
\section{Related Work}\label{sec:C4-related}
Prior research work tightly related to this work mainly falls into two
categories: 1) Low power high-level synthesis using multi-$V_{th}$ or
multi-$V_{dd}$; 2) Process variation aware high-level synthesis.

Shiue and Chakrabarti~\cite{hls:shiue00} proposed low-power scheduling schemes
with multi-$V_{dd}$ resources by maximizing the utilization of resources
operating at reduced supply voltages. Khouri et al.\cite{HLS:Khouri02}
performed high-level synthesis using a dual-$V_{th}$ library for leakage power
reduction. Tang et al.\cite{HLS:Tang05} formulated the synthesis problem using
dual-$V_{th}$ as a maximum weight independent set (MWIS) problem, within which
near-optimal leakage power reduction is achieved with greatly reduced run time.
Very recently, Shin et al. explored optimal register allocation for for
high-level synthesis using dual supply voltages~\cite{Shin09}. However, all of
these techniques were applied under deterministic conditions without taking
process variation into consideration.

Process variation aware high-level synthesis has recently gained much
attention. Jung et al.\cite{HLS:Jung07} proposed a timing yield aware HLS
algorithm to improve resource sharing and reduce overall latency. Gregory et
al.\cite{HLS:Greg09} integrated timing-driven floorplanning into the
variation-aware high-level design. Mohanty et al.'s work~\cite{HLS:Mohanty07}
took into account the leakage power variations in low-power high-level
synthesis, however, the major difference between~\cite{HLS:Mohanty07} and our
work is that, the delay variation of function units was not considered
in~\cite{HLS:Mohanty07}, so the timing analysis during synthesis was still
deterministic. Recently, Wang et al.\cite{HLS:Wang082} proposed a joint
design-time optimization and post-silicon tuning framework that tackles both
timing and power variations. Adaptive body biasing (ABB) was applied to
function units to reduce leakage power and improve power yield.

\section{Multi-$V_{th}$/$V_{dd}$ Library Characterization \\Under Process Variations}\label{sec:library}
%Scheduling and resource binding are key steps during the high-level synthesis process. The
%scheduler is in charge of determining the sequencing the operations of a control/data
%flow graph (CDFG) in control steps and within control steps (operator chaining) while obeying control and data dependencies and cycle constraints while optimizing for area/power/performance.
%%Cycle constraints are typically derived from latency and throughput constraints or from protocol requirements from interfaces, memories, fifos and other sequential components. In most cases the performance requirements are constraints and the goal of the optimization is to minimize area and power.
%The binding process binds operations to hardware units
%in the resource library to complete the mapping from abstracted
%descriptions of circuits into practical designs.
This section presents the characterization of the variation-aware
multi-$V_{th}$/$V_{dd}$ resource library, including the delay and power
characterization flow and
 the selection of dual threshold and supply voltages.%, and the statistical modeling of level converters needed in multi-$V_{dd}$ technique.

\subsection{Variation-aware Library Characterization Flow}

In order to fully explore the design space, a diverse library of functional
units is built for high-level synthesis. Each of the units can be characterized
as a $(delay, power)$ pair. Under the influence of process variations, the
delay and power of function units are no longer fixed values, but spread to
probabilistic distributions.
 Therefore, the characterization of
 function units with delay and power variations requires statistical analysis methodologies.

This work uses a commercial gate-level statistical timing analysis tool,
Synopsys PrimeTime \emph{VX}~\cite{URL:VX} to perform the characterization.
This variation-aware tool increases the accuracy of timing analysis by
considering the statistical distribution of characterized parameters, such as
channel length, metal-line width and oxide thickness.
Validation against SPICE Monte Carlo statistical analysis%~\cite{mc-book}
 shows that PrimeTime \emph{VX} analysis holds the similar accuracy but reduces
the running-time significantly.

The characterization flow takes as input the statistical distributions of
process parameters (channel length, oxide thickness, etc.) and generates the
statistical distributions of delay an power for each resource in the library.
To characterize the delay of function units under the impact of process
variations, the following steps are performed:
\begin{enumerate}
\item {All the standard cells in a technology library are characterized
    using variation aware analysis, and the results including parameters of
    cell delay distributions, are collected to build a variation-aware
    technology library. In this work, we use NCSU FreePDK 45nm technology
    library~\cite{URL:freepdk} for all the characterization and
    experiments.}
\item {The function units used in HLS are then synthesized and linked to
    the variation-aware technology library.}
\item {Statistical timing analysis for the function units is performed
    using PrimeTime \emph{VX}, and the parameters of delay distributions
    are reported.}
\end{enumerate}

Statistical power characterization for function units in the resource library
can be
done using Monte Carlo analysis in SPICE.%~\cite{mc-book}.
 The power consumption of function units consists of dynamic and leakage components.
While dynamic power is relatively immune to process variation, leakage power is
greatly affected and becomes dominant as technology continues scaling
down~\cite{HLS:Kim03}. Therefore, in this work only leakage power is
characterized using statistical analysis. However, this doesn't mean
considerations for dynamic power can be omitted. In fact, dynamic power
optimization in high-level synthesis has been a well explored
topic~\cite{HLS:newbook}. Our variation-oriented work emphasizing leakage power
optimization can be stacked on or integrated into existing power optimization
approaches in high-level synthesis, to further reduce the total power
consumption of circuits.

The power characterization flow is stated as follows. Process variations are
set in the MOS model files, and 1000 runs of Monte Carlo iterations are
performed for each library cell. After the characterization, the parameters of
the leakage power distributions of library cells are reported.

\subsection{Multi-$V_{th}/V_{dd}$ Library Characterization}

According to Berkeley short-channel BSIM4 model~\cite{PV:CLL+00}, higher
threshold voltages can lead to exponential reduction in leakage power, which is
given by
\begin{equation}\label{eq1}
I_{leakage} = I_0exp(\frac{V_{gs}-V_{th}}{nV_t})(1-exp(\frac{-V_{ds}}{V_t}))
\end{equation}
where $I_{leakage}$ is the gate leakage current, $V_{gs}$ and $V_{ds}$ are the
gate voltages, $V_t$ is the thermal voltage, $n$ is the subthreshold
coefficient and $I_0$ is a constant. Meanwhile, lower supply voltages will
result in a quadratic reduction in switching power and roughly a cubic
reduction in leakage power~\cite{HLS:Kulkarni04}. Previous implementations
using multiple threshold and supply voltages in conjunction have shown a very
effective reduction in both dynamic and leakage power~\cite{HLS:Srivastava04}.
Therefore, our approach considers the combination of dual threshold and dual
supply voltages, and characterizations are performed at the four ``corners'' of
voltage settings, namely $(V_{th}^L, V_{dd}^H), (V_{th}^H, V_{dd}^H),
(V_{th}^L, V_{dd}^L), (V_{th}^H, V_{dd}^L)$, where $(V_{th}^L, V_{dd}^H)$ is
the nominal case and the other three are low-power settings. Note that although
only 4 voltage settings are discussed in this work, it is natural to extend the
approach presented here to deal with more voltage settings. To reduce the
process technology cost, the multi-$V_{th}/V_{dd}$ techniques are applied at
the granularity of function units. That means, all the gates inside a function
unit operate at the same threshold and supply voltages. Voltages only differ
from function units to function units.

The selection of appropriate values of threshold and supply voltages for power
minimization has been discussed under deterministic
conditions~\cite{HLS:Srivastava04}. While the empirical models
in~\cite{HLS:Srivastava04} are validated on actual circuit
benchmarks~\cite{HLS:Kulkarni04}, they may not be accurate under the impact of
process variations. A refined model taking into account the process variations
is presented in~\cite{HLS:Srivastava07}, and this guides the optimal value
selection in this work.

The characterization results (which will be further discussed in
Section~\ref{sec:result}) show that, power reduction is always achieved at the
cost of delay penalties. Moreover, larger delay variations are observed for
slower units operating at high-$V_{th}$ or low-$V_{dd}$, which means larger
probability of timing violations when they are placed on the near-critical
paths. This further demonstrates the necessity of statistical analysis and
parametric yield-driven optimization approaches.

\section{Yield Analysis in Statistical High-Level Synthesis}\label{sec:yield}

In this section, a parametric yield analysis framework for statistical HLS
 is presented. We first show the necessity of statistical analysis
 by a simple motivational example, and then demonstrate the statistical
 timing and power analysis for HLS, as well as the modeling and integration of level converters for multi-$V_{dd}$ HLS.

\subsection{Parametric Yield}

\begin{figure}[tbp]
\centerline{\includegraphics[width=0.6\textwidth]{Chapter-4/Figures/yield.pdf}}
\caption{Motivating example of yield-driven synthesis.} \label{fig:C4-yield}
%\vspace{-8pt}
\end{figure}

To bring the process-variation awareness to the high-level synthesis flow, we
first introduce a new metric called \emph{Parametric Yield}. The parametric
yield is defined as the probability of the synthesized hardware meeting a
specified constraint $Yield = P(Y \leq Y_{max})$, where $Y$ can be delay or
power.

Fig.~\ref{fig:C4-yield} shows a motivational example of yield-aware analysis.
Three resource units $R1$, $R2$ and $R3$ have the same circuit implementation
but operate at different supply or threshold voltages.
 Fig.~\ref{fig:C4-yield} shows the delay an power distributions for $R1$, $R2$, $R3$. In this
case the mean power follows up $\mu_P(R3)<\mu_P(R2)<\mu_P(R1)$ and the mean
delay follows $\mu_D(R1)<\mu_D(R2)<\mu_D(R3)$ which is as expected since power
reduction usually comes at the cost of increased delay.
 The clock cycle  time $T_{CLK}$ and the power consumption constraint $P_{LMT}$ (e.g., the TDP (thermal design power) of most modern microprocessors) are
 also shown on the figure. If the variation is disregarded and nominal-case analysis is used, any of the resource units can be chosen since they all meet timing. In this case $R3$ would be chosen as it has the lowest power consumption. However, under a statistical point of view, $R3$ has a low timing yield (approximately 50\%) and is very likely to
 cause timing violations. In contrast, with corner-based worst-case analysis only $R1$ can be chosen under the clock cycle time constraint (the
 worst-case delay of $R2$ slightly violates the limit), whereas $R1$ has a poor power yield. In fact, if we set a timing yield constraint instead of
 enforcing the worst-case delay limitation, $R2$ can be chosen with a slight timing yield loss but a well balanced delay and power tradeoff. Therefore,
 a yield-driven statistical approach is needed for exploring the design space to maximize one parametric yield under other parametric yield constraints.


\subsection{Statistical Timing and Power Analysis for HLS}

High-level synthesis (HLS) is the process of transforming a behavioral
description into register level structure description. Operations such as
additions and multiplications in the DFG are scheduled into control steps.
During the resource allocation and binding stages, operations are bound to
corresponding function units in the resource library meeting type and latency
requirements.

Given the clock cycle time $T_{CLK}$, the timing yield of the entire DFG,
$Yield_{T}$ is defined as:
\begin{equation}\label{eq:tyield}
Yield_{T}=P(T_1 \leq T_{CLK}, T_2\leq T_{CLK},\ldots,T_n\leq T_{CLK})
\end{equation}
where $P()$ is the probability function, $T_1, T_2,\ldots,T_n$ are the arrival
time distributions at control step $1, 2,\ldots,n$, respectively.

\begin{figure*}[btp]
\centerline{\includegraphics[width=\textwidth]{Chapter-4/Figures/lcnew.pdf}}
 \caption{Timing yield computation in multi-$V_{dd}$ high-level
synthesis with different level conversions. Shadowed operations are bound to
function units with low supply voltages, and the bars indicate the insertion of
level converters.} \label{fig:lc} %\vspace{-10pt}
\end{figure*}

The arriving time distribution of each clock cycle can be computed from the
delay distributions of function units bound at that cycle. Two operations,
$sum$ and $max$, are used to compute the distributions:
\begin{itemize}
\item $sum$ operation is used when two function units are chained in
    cascade within a clock cycle, as shown in $CC1$ and $CC2$ of
    Fig.~\ref{fig:lc}. The total delay can be computed as the ``sum'' of
    their delay distributions (normal distribution assumed);
\item $max$ operation is used when the outputs of two or more units are fed
    to another function unit at the same clock cycle, as shown in $CC1$ of
    Fig.~\ref{fig:lc}. The ``maximum'' delay distribution can be computed
    out of the contributing distributions using tightness probability and
    moment matching~\cite{HLS:Wang082}.
\end{itemize}
With these two operations, the arriving time distribution of each clock cycle
is computed, and the overall timing yield of the DFG is obtained using
Equation~(\ref{eq:tyield}).

The total power consumption of a DFG can be computed as the sum of the power
consumptions of all the function units used in the DFG. Given a power
limitation $P_{LMT}$, the power yield of the DFG $Yield_P$ is computed as the
probability that total power $P_{DFG}$ is less than the requirement, as
expressed in Equation~(\ref{eqq2}).
\begin{equation}\label{eqq2}
Yield_P = P(P_{DFG} \leq P_{LMT})
\end{equation}
Since dynamic power is relatively immune to process variations, it is regarded
as a constant portion which only affects the mean value of the total power
consumption. Therefore, the total power is still normally distributed, although
statistical analysis is only applied to the leakage power. As aforementioned in
Section~\ref{sec:library}, our proposed yield-driven statistical framework can
be stacked on existing approaches for dynamic power optimization, to further
reduce the total power consumption of circuits.

\subsection{Voltage Level Conversion in HLS}
In designs using multi-$V_{dd}$ resource units, voltage level convertors are
required when a low-voltage resource unit is driving a high-voltage resource
unit. Level conversion can be performed either synchronously or asynchronously.
Synchronous level conversion is usually embedded in flip-flops and occurs at
the active clock edge, while asynchronous level converters can be inserted
anywhere within the combinational logic block.

 When process variations are
considered, asynchronous level converters are even more favorable, because they
are not bounded by clock edges, and timing slacks can be passed through the
converters. Therefore, time borrowing can happen between low-voltage and
high-voltage resource units. As slow function units (due to variations) may get
more time to finish execution, the timing yield can be improved and the impact
of process variations is consequently reduced.

While many fast and low-power level conversion circuits have been proposed
recently, this work uses the multi-$V_{th}$ level converter presented
in~\cite{HLS:Tawfik07}, taking the advantage that there is no extra process
technology overhead for multi-$V_{th}$ level converters, since multi-$V_{th}$
is already deployed for function units. The proposed level converter is
composed of two dual-$V_{th}$ cascaded inverters. Its delay and power are then
characterized in HSPICE using the listed parameters~\cite{HLS:Tawfik07}.

The delay penalty of a level converter can be accounted by summing its delay
with the delay of the function unit it is associated to. The power penalty can
be addressed by counting the level converters used in the DFG and adding the
corresponding power to the total power consumption.

%\vspace{5pt}
\section{Yield-Driven Power Optimization Algorithm}\label{sec:framework}

In this section we propose our yield-driven power optimization framework based
on the aforementioned statistical timing and power yield analysis. During the
high-level synthesis design loop, resource binding selects the optimal resource
instances in the resource library and binds them to the scheduled operations at
each control step. A variation-aware resource binding algorithm is then
proposed to maximize power yield under a preset timing yield constraint, by
iteratively searching for the operations with the maximum potential of
timing/power yield improvement, and replacing them with better candidates in
the multi-$V_{th}/V_{dd}$ resource library.

\subsection{Overview of the Variation-aware Resource Binding Algorithm}
Our variation-aware resource binding algorithm takes a search strategy called
\emph{variable depth search}~\cite{op-book,HLS:Raghunathan95,HLS:Wang082} to
iteratively improve the power yield under performance constraints.
 The outline of the algorithm is shown in Fig.~\ref{fig:algorithm},
where a DFG is initially scheduled and bound to resource library with nominal
voltages $(V_{th}^L, V_{dd}^H)$. A lower-bound constraint on the timing yield
is set, so that the probability of the design can operate at a given clock
frequency, will be larger than or equal to a preset threshold (e.g., 95\%). In
the algorithm, a move is defined as a local and incremental change on the
resource bindings. As shown in the sub-routine $\proc{GenMove}$ in
Fig.~\ref{fig:algorithm}, the algorithm generates a set of moves, and finds out
a sequence of moves that maximizes the accumulated $gain$, which is defined as
$\alpha *\Delta Yield_D + \Delta Yield_P$, where $\alpha$ is a weighting factor
to balance the weights of timing and power yield improvements. The optimal
sequence of moves is then applied to the DFG, and the timing and power yields
of the DFG are updated before the next iteration. The iterative search ends
when there is no yield improvement or the timing yield constraint is violated.

\begin{figure}[htbp]
\centering
\footnotesize
\rule[-1mm]{\textwidth}{0.01in}
\begin{codebox}
\Procname{$\proc{VABinding}(DFG, ResLib, Constraints, LCStrategy)$}
\zi \Comment Initialization
\li Scheduling using ASAP strategy
\li Initial Binding to $(V_{th}^L, V_{dd}^H)$ resources
\zi \Comment Variation-aware resource binding
\li \While $\Delta Yield_P > 0$ AND $Yield_D \geq Constraint$
\li \Do    \For $i \gets 1$ to $MAXMOVES$
\li    \Do  $Gain_i \gets \proc{GenMove}(DFG, ResLib, LCStrategy)$
\li          Append $Gain_i$ to $Gain\_List$;
     \End
\li     Find subsequence $Gain_1,\ldots,Gain_k$ in $Gain\_List$
\zi     so that $G=\sum_{i=1}^k Gain_i$ is maximized
\li    \If $G > 0$
\li     \Do Accept moves $1\ldots k$
\li         Evaluate $\Delta Yield_P$ and $Yield_D$
        \End
\End
\end{codebox}
\begin{codebox}
\Procname{$\proc{GenMove}(DEG, ResLib, LCStrategy)$}
\li MOVE: Choose a move using steepest descent heuristic~\cite{op-book}
\li Check whether and where level conversion is needed
\li \If $LCStrategy = Avoidance$ AND $NeedConversion$
\li    \Do \Goto MOVE
        \End
\li \If $LCStrategy = Synchronous$ AND $NeedConversion$
\zi \Comment Check whether conversion is synchronous or not
\li \Do \If Conversion is inside operation chaining
\li      \Do \Goto MOVE
    \End \End
\li Count the overhead of level conversion
\li Evaluate the $Gain$ of this move
\li Return $Gain$
\End
\end{codebox}
\rule[1mm]{\textwidth}{0.01in}
\vspace{-8pt}
\caption{Outline of the variation-aware resource binding algorithm}\label{fig:algorithm}
%\vspace{-15pt}
\end{figure}

\subsection{Voltage Level Conversion Strategies}
Moves during the iterative search may result in low-voltage resource units
driving high-voltage resource units. Therefore, level conversion is needed
during resource binding. However, if resources are selected and bound so that
low-voltage resource units never drive high-voltage ones, level conversion will
not be necessary and the delay and power overheads brought by level converters
can be avoided. This reduces the flexibility of resource binding for
multi-voltage module combinations, and may consequently decrease the attainable
yield improvement. The trade-off in this conversion-avoidance strategy, can be
explored and evaluated within our proposed power optimization algorithm.

We also incorporate other two strategies of level conversions in the power
optimization algorithm for comparison. All the three strategies are listed as
follows:
\begin{itemize}
\item \textbf{Level Conversion Avoidance}. Resource binding is performed
    with the objective that low-voltage resources never drive high-voltage
    ones. As shown in Fig~\ref{fig:lc}(a), no dark-to-light transition
    between operations is allowed (while dark operations are bound to
    low-$V_{dd}$ units), so that level conversion is avoided. This is the
    most conservative strategy.

\item \textbf{Synchronous Level Conversion}. Voltage level conversion is
    done synchronously in the level-converting flip-flops (SLCs). As shown
    in Fig.~\ref{fig:lc}(b), the dark-to-light transition only happens at
    the beginning of each clock cycles. The flip-flop structure proposed
    in~\cite{HLS:Ishihara04} is claimed to have smaller delay than the
    combination of an asynchronous converter and a conventional flip-flop.
    However, as discussed previously, synchronous level conversion may
    reduce the flexibility of resource binding as well as the possibility
    of timing borrowing. The effectiveness of this strategy is to be
    explored by the optimization algorithm.

\item \textbf{Asynchronous Level Conversion}. Asynchronous level converters
    (ALCs) are inserted wherever level conversion is needed, as
    dark-to-light transition can happen anywhere in Fig.~\ref{fig:lc}. This
    aggressive strategy provides the maximum flexibility for resource
    binding and timing borrowing. Although it brings in delay and power
    overhead, it still has great potential for timing yield improvement.
\end{itemize}

\subsection{Moves Used in the Iterative Search}

In order to fully explore the design space, three types of moves are used in
the iterative search for resource binding:
\begin{itemize}
\item \textbf{Resource Rebinding}. In this move, an operation is assigned
    to a different function unit in the library with different timing and
    power characteristics. The key benefit of the multi-$V_{th}/V_{dd}$
    techniques is that it provides an enlarged design space for
    exploration, and optimal improvements are more likely to be obtained.
\item \textbf{Resource Sharing}. In this move, two function units that are
    originally bound to different function units, are now merged to share
    the same function unit. The type of move reduces the resource usage and
    consequently improves the power yield.
\item \textbf{Resource Splitting}. In this move, the operation that
    originally shared function unit with other operations, is split from
    the shared function unit. This type of move might lead to other moves
    such as resource rebinding and resource sharing.
\end{itemize}

After each move, the algorithm checks where the low supply-voltage function
units are used, and decides whether to insert or remove the level converters,
according to the predefined level conversion strategy. If a move is against the
strategy, it is revoked and new moves are generated until a qualifying move is
found.

\subsection{Algorithm Analysis}

It has to be noted that, in the procedure $\proc{GenMove}$ shown in
Fig.~\ref{fig:algorithm}, even though the returned $Gain$ might be negative, it
still could be accepted. Since the sequence of a cumulative positive gain is
considered, the negative gains help the algorithm escape from local minima
through hill-climbing.

As for the computational complexity, it is generally not possible to give
non-trivial upper bounds of run time for local search
algorithms~\cite{op-book}. However, for variable depth search in general graph
partitioning, Fiduccia and Mattheyses~\cite{op-book} found a near-optimal
growth rate of run time to be $O(n\log n)$, where $n$ is the number of nodes in
the graph. In our proposed algorithm, the timing and power yield evaluation, as
well as the level converter insertion, are performed at each move. Since the
yield can be updated using a gradient computation approach~\cite{HLS:Wang082},
the run time for each move is at most $O(n)$. Therefore, the overall run time
for the proposed resource binding algorithm is $O(n^2\log n)$.

%\vspace{5pt}
\section{Experimental Results}\label{sec:result}

\begin{figure}[tbp]
  % Requires \usepackage{graphicx}
  \centering
  \includegraphics[width=0.75\textwidth]{Chapter-4/Figures/charac.pdf}\\
%  \vspace{-5pt}
  \caption{Delay and leakage power characterization of function units with multi-$V_{th}/V_{dd}$ and variation awareness.}\label{fig:charact}
%  \vspace{-8pt}
\end{figure}

In this section, we present the experimental results of our variation-aware
power optimization framework for high-level synthesis. The results show that
our method can effectively improve the overall power yield of given designs and
reduce the impact of process variations.

We first show the variation-aware delay and power characterization of function
units. The characterization is based on NCSU FreePDK 45nm technology
library~\cite{URL:freepdk}. Variations on two device parameters, \emph{channel
length} and \emph{oxide thickness}, are set with relative deviations
($\sigma$/$mu$) to be $5\%$, respectively. The voltage corners for the
characterization are set as: $V_{th}^L = 0.37V$, $V_{th}^H = 0.56V$, $V_{dd}^L
= 0.9V$, $V_{dd}^H = 1.1V$. The characterization results for five function
units, including two 16-bit adders \emph{bkung} and \emph{kogge}, two
8-bit$\times$8-bit multipliers \emph{pmult} and \emph{booth}, and one 16-bit
multiplexer \emph{mux21}, are depicted in Fig.~\ref{fig:charact}. In the
figures, the color bars show the nominal case values while the error-bars show
the deviations. It is clearly shown that with lower $V_{dd}$ and/or higher
$V_{th}$, significant power reductions are achieved at the cost of delay
penalty.

With the variation-aware multi-$V_{th}/V_{dd}$ resource library characterized,
our proposed resource binding algorithm is applied on a set of industrial
high-level synthesis benchmarks. A total power limitation $P_{LMT}$ is set for
each benchmark to evaluate the power yield improvement. The dynamic power
consumption of function units is estimated by Synopsys \emph{Design Compiler}
with multi-$V_{th}/V_{dd}$ technology libraries generated by \emph{Liberty
NCX}. In this work with FreePDK 45nm technology, the dynamic power is about 2
times of the mean leakage power. The power yield before and after the
improvement, is then computed using Equation~(\ref{eqq2}) in
Section~\ref{sec:yield}-B. The proposed resource binding algorithm is
implemented in C++ and experiments are conducted on a Linux workstation with
Intel Xeon 3.2GHz processor and 2GB RAM. All the experiments run in less than
60s of CPU time.

\begin{table*}[tbp]
\centering \footnotesize \caption{The usage of function units and level
converters with different level conversion strategies}\label{table:usage}
 \vspace{7pt}
\begin{tabular}{|c|c|c||c|c|c||c|c|c|c|}
\hline
Bench & \multicolumn{2}{|c||}{LC-Avoidance} & \multicolumn{3}{|c||}{LC-Synchronous} & \multicolumn{4}{|c|}{LC-Asynchronous} \\ \cline{2-10}
Name & Vdd-H & Vdd-L & Vdd-H & Vdd-L & LCs & Vdd-H & Vdd-L & LCs & Overhead \\ \hline\hline
EWF & 6 & 1 & 4 & 3 & 1 & 3 & 4 & 2         & 3.7\%   \\ \hline
WANG & 9 & 2 & 8 & 3 & 2 & 5 & 6 & 3        & 3.4\%   \\ \hline
MCM & 20 & 4 & 16 & 8 & 4 & 15 & 9 & 5      & 2.4\%   \\ \hline
DIR & 28 & 4 & 20 & 12 & 8 & 14 & 18 & 12   & 4.8\%   \\ \hline
STEAM & 34 & 8 & 25 & 19 & 11 & 21 & 23 & 13& 5.0\%   \\ \hline
\end{tabular}
%\vspace{-10pt}
\end{table*}

We compare our variation-aware resource binding algorithm against the
traditional deterministic approach, which uses the worst-case ($\mu$+3$\sigma$)
delay values of function units in the multi-$V_{th}/V_{dd}$ library to guide
the resource binding. Worst-cased based approach will naturally lead to 100\%
timing yield, however, the power yield is poor as shown in the motivational
example in Fig.~\ref{fig:C4-yield}. In contrast, our yield-aware statistical
optimization algorithm takes the delay and power distributions as inputs,
explores the design space with the guidance of \emph{YieldGain}, and
iteratively improves the power yield under a slight timing yield loss. The
comparison results are shown in Fig.~\ref{fig:result1}-\ref{fig:result3},
respectively.


\begin{figure}[!btp]
  % Requires \usepackage{graphicx}
  \centering
  \includegraphics[width=0.65\textwidth]{Chapter-4/Figures/result1.pdf}
%    \vspace{-10pt}
  \caption{Power yield improvement against deterministic worst-case approach with different level conversion strategies and timing yield constraint of 95\%.}\label{fig:result1}
%    \vspace{-10pt}
\end{figure}

Fig.~\ref{fig:result1} shows the power yield improvement against worst-case
delay based approach, with different level conversion strategies. A fixed
timing yield constraint of 95\% is set for the proposed variation-aware
algorithm. The usage of function units and level converters under the three
listed conversion strategies (conversion avoidance, synchronous conversion and
asynchronous conversion) is listed in Table~\ref{table:usage}, in which ``\#
Vdd-H FUs'' and ``\# Vdd-L FUs'' show the numbers of function units with
high/low supply voltages, respectively, and ``\# LCs'' counts the number of
converters used in the design. The last column counts the total power overhead
of the asynchronous level converters. The average power yield improvements for
the three strategies are 10.3\%, 16.7\% and 21.5\%, respectively. From
Fig.~\ref{fig:result1} and Table~\ref{table:usage} we can see that larger power
yield improvements can be achieved when more low-Vdd function units are used in
the design. The results also validate our claims in Section~\ref{sec:yield}-C
and Section~\ref{sec:framework}-B that, asynchronous level conversion is more
favorable in statistical optimization, because it enables timing borrowing
between function units, and leads to the timing yield improvement that can
compensate the overhead of the converters. Therefore, compared to the
synchronous case, more asynchronous converters are used while yielding better
results.


\begin{figure}[!btp]
  % Requires \usepackage{graphicx}
  \centering
  \includegraphics[width=0.65\textwidth]{Chapter-4/Figures/result2.pdf}
%    \vspace{-10pt}
  \caption{Power yield improvement against deterministic worst-case approach with multi-$V_{th}$ only and different timing yield constraints.}\label{fig:result2}
%    \vspace{-5pt}
\end{figure}


\begin{figure}[!btp]
  % Requires \usepackage{graphicx}
  \centering
  \includegraphics[width=0.65\textwidth]{Chapter-4/Figures/result3.pdf}
%    \vspace{-10pt}
  \caption{Power yield improvement against deterministic worst-case approach with asynchronous level conversion and different timing yield constraints.}\label{fig:result3}
%    \vspace{-10pt}
\end{figure}

%
Fig.~\ref{fig:result2} shows power yield improvement with multi-$V_{th}$
technique only, which means only the resource units with nominal supply voltage
$V_{dd}^H$ can be selected. In this case, no level conversion is needed so
there is no overhead for level converters. The average power yield improvements
against worst-case delay based approach, under timing yield constraints 99\%,
95\% and 90\% are 6.6\%, 8.5\% and 11.0\%, respectively. At timing yield 95\%,
the average power yield improvement (8.5\%) is smaller than the LC-Avoidance
case (10.3\%) in Fig.~\ref{fig:result1}, which shows that using multi-$V_{dd}$
resource units can further improve the power yield.

Fig.~\ref{fig:result3} shows the power yield improvement against worst-case
delay based approach, under different timing yield constraints. Asynchronous
level conversion is chosen in this series of experiments. The average power
yield improvements under timing yield constraints 99\%, 95\% and 90\% are
11.7\%, 21.0\% and 27.2\%, respectively. It is clearly shown that, the power
yield improvement largely depends on how much timing yield loss is affordable
for the design. This will further push forward the design space exploration for
a well balanced timing and power trade-off.

\section{Summary}
This chapter investigated the impact of process variations on
multi-$V_{th}/V_{dd}$ techniques for low power high-level synthesis. We
characterize delay and power variations of function units under different
threshold and supply voltages, and feed the variation-characterized resource
library to the HLS design loop. Statistical timing and power analysis for
high-level synthesis is then introduced, to help our proposed resource binding
algorithm explore the design space, and maximize the power yield of designs
under given timing yield constraints. Experimental results show that
significant power reduction can be achieved with the proposed variation-aware
framework, compared with traditional worst-case based deterministic approaches.
